"""
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
"""

from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1:
            return intervals
        # 先保证第一个元素递增
        intervals.sort()
        merges = []
        for interval in intervals:
            # 最后一个元素的比较
            if not merges or merges[-1][-1] < interval[0]:
                merges.append(interval)
            else:
                merges[-1][-1] = max(merges[-1][-1], interval[1])
        return merges


if __name__ == "__main__":
    # intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
    # intervals = [[1, 4], [0, 4]]
    # intervals = [[1, 4], [2, 3]]
    intervals = [[1, 4], [0, 2], [3, 5]]
    # intervals = [[1, 4], [5, 6]]
    print(Solution().merge(intervals))
